/*
 * The class stands for the regular graph
 */

package cz.muni.fi.xkadlec6.bp.regularExpression;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import cz.muni.fi.xkadlec6.bp.alphabet.AlphabetGenerator;
import cz.muni.fi.xkadlec6.bp.automaton.Automaton;
import cz.muni.fi.xkadlec6.bp.automaton.NoSuchStateException;

/**
 * The class represents the regular graph, it os supporting class for the class RegularExpressionConverter
 * 
 * @author Jana Kadlecova
 */
public class RegularGraph
{

	// automaton with one final and one start state
	private Automaton automaton;
	private Map<String, Map<String, List<Node>>> transitions;
	private String finalState; // new final state of automaton
	private String oldStartState; // old start state of automaton
	private IDGenerator i = new IDGenerator();

	/**
	 * Constructor, initializes atributes, makes new regular graph with one new start state and one new final state (DFA
	 * -> RE)
	 * 
	 * @param a
	 *            the deterministic automaton
	 */
	public RegularGraph(Automaton a)
	{
		if (a == null)
		{
			throw new NullPointerException("RegularGraph()");
		}
		if (!a.isDeterministic())
		{
			throw new IllegalArgumentException("RegularGraph(): given " + "automaton is not deterministic: " + a);
		}
		this.automaton = new Automaton(a);
		this.transitions = new HashMap<String, Map<String, List<Node>>>();
		this.oldStartState = automaton.getStartState();
		this.setNewStartState();
		this.setNewFinalState();
	}

	/**
	 * sets new start state and adds new the transition from new beginning state to old start state under epsilon
	 */
	private void setNewStartState()
	{
		newStartState = this.automaton.generateUniqueState("x");
		this.automaton.addState(newStartState);
		try
		{
			this.automaton.setStartState(newStartState);
			this.automaton.addEpsilon(newStartState, this.oldStartState);
		}
		catch (NoSuchStateException e)
		{
			throw new Error("RegularGraph.setNewStartState(): " + e.getMessage());
		}
	}

	/**
	 * sets the new final state and adds transitions from old final states to new final state under epsilon
	 */
	private void setNewFinalState()
	{
		// new final state is generated
		this.finalState = this.automaton.generateUniqueState("y");
		// new final state is added to the automaton
		this.automaton.addState(this.finalState);
		try
		{
			// transitions from the old final states to new final states under
			// epsilon are added and old final states are removed from the final
			// states
			for (String oldFinalState : new HashSet<String>(this.automaton.getFinalStates()))
			{
				this.automaton.addEpsilon(oldFinalState, this.finalState);
				this.automaton.removeFinalState(oldFinalState);
			}
			this.automaton.addToFinalStates(finalState);
		}
		catch (NoSuchStateException e)
		{
			throw new Error("RegularGraph.setNewFinalState(): " + e.getMessage());
		}
	}

	private void removeUnreachableStatesAndBlackHoles()
	{
		this.automaton.removeUnreachableStates();
		List<String> tryStates = new ArrayList<String>();
		tryStates.add(finalState);
		Set<String> reachable = new HashSet<String>();
		reachable.add(finalState);
		while (!tryStates.isEmpty())
		{
			Set<String> ancestors = this.getAncestors(tryStates.get(0));
			for (String s : ancestors)
			{
				if (!reachable.contains(s))
				{
					tryStates.add(s);
					reachable.add(s);
				}
			}
			tryStates.remove(tryStates.get(0));
		}
		if (!reachable.contains(oldStartState))
		{
			for (String s : new HashSet<String>(automaton.getStates()))
			{
				if (!s.equals(oldStartState) && !s.equals(automaton.getStartState()))
				{
					try
					{
						automaton.removeState(s);
					}
					catch (NoSuchStateException e)
					{
						throw new Error("RegularGraph.removeBlack...." + e.getMessage());
					}
				}
			}
		}
		else
		{
			for (String s : new HashSet<String>(automaton.getStates()))
			{
				if (!reachable.contains(s))
				{
					try
					{
						automaton.removeState(s);
					}
					catch (NoSuchStateException e)
					{
						throw new Error("RegularGraph.removeBlack...." + e.getMessage());
					}
				}
			}

		}
	}

	/**
	 * Converts regular graph to the regular expression
	 * 
	 * @return regular expression
	 */
	public RegularExpression reduct()
	{
		this.removeUnreachableStatesAndBlackHoles();
		this.setNodes();

		Comparator<String> c = AlphabetGenerator.getComparator(automaton.getStatesType());
		SortedSet<String> states = Collections.checkedSortedSet(new TreeSet<String>(c), String.class);
		states.addAll(automaton.getStates());
		states.remove(finalState);
		states.remove(automaton.getStartState());
		for (String s : states)
		{

			this.reductState(s);
		}
		this.setNodeFromXToY();
		RegularExpression RE = new RegularExpression(transitions.get(automaton.getStartState()).get(finalState).get(0));
		return RE;
	}

	/**
	 * sets the transition state1 -> (state2 -> regular exression)
	 */
	private void setNodes()
	{
		SortedSet<String> a = AlphabetGenerator.sortSet(automaton.getAlphabet(), automaton.getAlphabetType());
		a.add("epsilon");
		for (String from : automaton.getStates())
		{
			if (!from.equals(finalState))
			{
				this.transitions.put(from, new HashMap<String, List<Node>>());
				for (String under : a)
				{
					try
					{
						for (String to : automaton.getStates(from, under))
						{
							if (!transitions.get(from).containsKey(to))
							{
								this.transitions.get(from).put(to, new ArrayList<Node>());
							}
							Node n = new Node(under, false, i);
							this.transitions.get(from).get(to).add(n);
						}
					}
					catch (NoSuchStateException e)
					{
						throw new Error("setNodes(): " + e.getMessage());
					}
				}
			}
		}
	}

	/**
	 * reducts state to remove in the regular graph
	 * 
	 * @param removed_state
	 */
	private void reductState(String removed_state)
	{
		if (removed_state.equals(automaton.getStartState()) || removed_state.equals(finalState))
		{
			throw new IllegalArgumentException("RegularGraph()reductState(): " + removed_state);
		}
		HashSet<String> states_leading_to_removed = new HashSet<String>();
		for (String s : transitions.keySet())
		{
			if (!s.equals(removed_state))
			{
				if (transitions.get(s).containsKey(removed_state))
				{
					states_leading_to_removed.add(s);
				}
			}
		}
		HashSet<String> states_leading_from_removed = new HashSet<String>(transitions.get(removed_state).keySet());
		states_leading_from_removed.remove(removed_state);
		this.setIterationNode(removed_state);
		for (String from : states_leading_to_removed)
		{
			for (Node node_from : new HashSet<Node>(transitions.get(from).get(removed_state)))
			{
				for (String to : states_leading_from_removed)
				{
					for (Node node_to : new HashSet<Node>(transitions.get(removed_state).get(to)))
					{
						Node n1 = new Node(node_from, i);
						Node n2 = new Node(node_to, i);
						Node it = new Node(transitions.get(removed_state).get(removed_state).get(0), i);
						Node krat = new Node(".", true, i);
						Node krat2 = new Node(".", true, i);
						krat.addChildren(n1, it);
						krat2.addChildren(krat, n2);
						if (transitions.get(from).containsKey(to))
						{
							transitions.get(from).get(to).add(krat2);
						}
						else
						{
							transitions.get(from).put(to, new ArrayList<Node>());
							transitions.get(from).get(to).add(krat2);
						}
					}
				}
			}
		}
		for (String state : states_leading_to_removed)
		{
			transitions.get(state).remove(removed_state);
		}
		transitions.remove(removed_state);
	}

	private void setIterationNode(String state)
	{
		Node iteration_node = new Node("*", true, i);
		Node emptySet_node = new Node("\\0", false, i);
		if (transitions.get(state).containsKey(state))
		{
			ArrayList<Node> nodes = new ArrayList<Node>(transitions.get(state).get(state));
			while (nodes.size() >= 2)
			{
				Node n1 = nodes.get(0);
				Node n2 = nodes.get(1);
				Node n3 = new Node("+", true, i);
				n3.addChildren(n1, n2);
				nodes.add(0, n3);
				nodes.remove(n2);
				nodes.remove(n1);

			}
			Node n = new Node("+", true, i);
			n.addChildren(nodes.get(0), emptySet_node);
			iteration_node.addChildren(n);
		}
		else
		{
			iteration_node.addChildren(emptySet_node);
		}
		transitions.get(state).put(state, new ArrayList<Node>());
		transitions.get(state).get(state).add(iteration_node);

	}

	private void setNodeFromXToY()
	{
		Node emptySet_node = new Node("\\0", false, i);
		Node n;
		if (!transitions.containsKey(automaton.getStartState()))
		{
			throw new IllegalArgumentException("setNodeFromXToY");
		}
		if (!transitions.get(automaton.getStartState()).containsKey(finalState))
		{
			transitions.get(automaton.getStartState()).put(finalState, new ArrayList<Node>());
		}
		if (transitions.get(automaton.getStartState()).get(finalState).size() >= 1)
		{
			ArrayList<Node> nodes = new ArrayList<Node>(transitions.get(automaton.getStartState()).get(finalState));
			while (nodes.size() >= 2)
			{
				Node n1 = nodes.get(0);
				Node n2 = nodes.get(1);
				Node n3 = new Node("+", true, i);
				n3.addChildren(n1, n2);
				nodes.add(0, n3);
				nodes.remove(n2);
				nodes.remove(n1);
			}
			n = new Node("+", true, i);
			n.addChildren(nodes.get(0), emptySet_node);
		}
		else
		{
			n = emptySet_node;
		}
		transitions.get(automaton.getStartState()).put(finalState, new ArrayList<Node>());
		transitions.get(automaton.getStartState()).get(finalState).add(n);

	}

	private Set<String> getAncestors(String state)
	{
		Set<String> ancestors = new HashSet<String>();
		Set<String> alp = new HashSet<String>(automaton.getAlphabet());
		alp.add("epsilon");
		for (String from : automaton.getStates())
		{
			for (String under : alp)
			{
				try
				{
					for (String to : automaton.getStates(from, under))
					{
						if (to.equals(state))
						{
							ancestors.add(from);
						}
					}
				}
				catch (NoSuchStateException e)
				{
					throw new Error("RegularGraph.getAncestors(): " + e.getMessage());
				}
			}
		}
		return ancestors;
	}

	// REG -> EFA
	private RegularExpression re;
	private String newStartState;
	private SortedSet<String> alphabet;
	private int alphabetSize;
	private Map<String, Map<String, Set<Node>>> transitions2;

	/**
	 * Makes new Regular graph, for the converting RE -> NFA with epsilon-transitions
	 * 
	 * @param regularExpression
	 */
	public RegularGraph(RegularExpression regularExpression)
	{
		if (regularExpression == null)
		{
			throw new NullPointerException("RegularGraph(): the given regular " + "expression is null.");
		}
		this.re = new RegularExpression(new Node(regularExpression.getStartNode(), i));
		this.transitions2 = new HashMap<String, Map<String, Set<Node>>>();
		alphabet = AlphabetGenerator.getLetterWithIndex(5, "s");
		alphabetSize = alphabet.size();
		this.setTransitions();
	}

	// the RE -> NFA
	private void setTransitions()
	{
		this.newStartState = this.getState();
		this.finalState = this.getState();
		this.transitions2.put(newStartState, new HashMap<String, Set<Node>>());
		this.transitions2.get(newStartState).put(finalState, new HashSet<Node>());
		this.transitions2.get(newStartState).get(finalState).add(re.getStartNode());
	}

	private String getState()
	{
		if (alphabet.isEmpty())
		{
			alphabet = AlphabetGenerator.getLetterWithIndex(alphabetSize * 2, "s");
			alphabet.removeAll(AlphabetGenerator.getLetterWithIndex(alphabetSize, "s"));
			alphabetSize = alphabetSize * 2;
		}
		String s = alphabet.first();
		alphabet.remove(s);
		return s;
	}

	/**
	 * converts the regular graph to the NFA (with epsilon-transitions)
	 * 
	 * @return NFA (with epsilon-transitions)
	 */
	public Automaton transform()
	{
		this.automaton = new Automaton(this.newStartState);
		this.automaton.addState(finalState);
		try
		{
			this.automaton.addToFinalStates(finalState);
		}
		catch (NoSuchStateException e)
		{
			throw new Error("RegularGraph.transform(): " + e.getMessage());
		}
		if (re.getStartNode().getName().equals("\\0"))
		{
			return automaton;
		}
		if (re.getStartNode().getName().equals("epsilon"))
		{
			try
			{
				automaton.addEpsilon(newStartState, finalState);
			}
			catch (NoSuchStateException e)
			{
				throw new Error("RegularGraph.transform(): " + e.getMessage());
			}
			return automaton;
		}
		this.transformTransition(newStartState, finalState, re.getStartNode());
		return this.automaton;
	}

	private void transformTransition(String from, String to, Node n)
	{
		if (n == null)
		{
			return;
		}
		if (!transitions2.containsKey(from))
		{
			return;
		}
		if (!transitions2.get(from).containsKey(to))
		{
			return;
		}
		if (!transitions2.get(from).get(to).contains(n))
		{
			return;
		}
		if (!n.isOperation())
		{
			this.automaton.addState(from);
			this.automaton.addState(to);
			try
			{
				if (!n.getName().equals("\\0"))
				{
					this.automaton.addTransition(from, n.getName(), to);
				}
			}
			catch (NoSuchStateException e)
			{
				throw new Error("RegularGraph.transformTransition(): " + e.getMessage());
			}
		}
		else
		{
			if (n.getName().equals("+"))
			{
				this.transformUnion(from, to, n);
			}
			if (n.getName().equals("."))
			{
				this.transformConcatenation(from, to, n);
			}
			if (n.getName().equals("*"))
			{
				this.transformStar(from, to, n);
			}
		}
	}

	private void transformStar(String from, String to, Node n)
	{
		List<Node> children = n.getChildren();
		Node n1 = children.get(0);
		try
		{
			this.automaton.addState(from);
			this.automaton.addState(to);
			String s = this.getState();
			this.automaton.addState(s);
			this.automaton.addEpsilon(from, s);
			this.automaton.addEpsilon(s, to);

			this.transitions2.put(s, new HashMap<String, Set<Node>>());
			this.transitions2.get(s).put(s, new HashSet<Node>());
			this.transitions2.get(s).get(s).add(n1);

			this.transformTransition(s, s, n1);
		}
		catch (NoSuchStateException e)
		{
			throw new Error("RegularGraph.transformStar(): " + e.getMessage());
		}
	}

	private void transformConcatenation(String from, String to, Node n)
	{
		List<Node> children = n.getChildren();
		Node n1 = children.get(0);
		Node n2 = children.get(1);
		String s = this.getState();

		this.transitions2.get(from).put(s, new HashSet<Node>());
		this.transitions2.get(from).get(s).add(n1);

		this.transitions2.put(s, new HashMap<String, Set<Node>>());
		this.transitions2.get(s).put(to, new HashSet<Node>());
		this.transitions2.get(s).get(to).add(n2);

		this.transformTransition(from, s, n1);
		this.transformTransition(s, to, n2);
	}

	private void transformUnion(String from, String to, Node n)
	{
		List<Node> children = n.getChildren();
		Node n1 = children.get(0);
		Node n2 = children.get(1);

		this.transitions2.get(from).get(to).add(n1);
		this.transitions2.get(from).get(to).add(n2);

		this.transformTransition(from, to, n1);
		this.transformTransition(from, to, n2);
	}
}
